/*
 * 字符的着色
 * 此文件由 regcomp.c 引用。
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 *
 * 本软件的开发部分由 Cray Research Inc.、
 * UUNET Communications Services Inc.、Sun Microsystems Inc. 和 Scriptics
 * Corporation 提供资金，以上公司对结果不承担任何责任。作者
 * 感谢他们的支持。
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * 我希望在使用此软件的文档中给予我相应的荣誉，
 * 但这并不是一项要求。
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, 或利润；
 * 或业务中断) 造成的损害，无论在任何理论责任下，
 * 无论在合同、严格责任或侵权（包括过失或其他）下，均不负任何责任，
 * 即使在被告知此类损害的可能性的情况下。
 *
 * src/backend/regex/regc_color.c
 *
 *
 * 请注意，这段代码与 NFA arc 维护之间存在一些复杂的关系，
 * 这或许应该在某个时候清理。
 */



#define CISERR()	VISERR(cm->v)
#define CERR(e)		VERR(cm->v, (e))



/*
 * initcm - 设置新的颜色映射
 */
static void initcm(struct vars *v,
	   struct colormap *cm)
{
	struct colordesc *fc_cd;

	cm->magic = CMMAGIC;
	cm->v = v;

	cm->ncds = NINLINECDS;
	cm->cd = cm->cdspace;
	cm->max = 0;
	cm->free = 0;

	fc_cd = cm->cd;				/* cm->cd[WHITE] */
	fc_cd->nschrs = MAX_SIMPLE_CHR - CHR_MIN + 1;
	fc_cd->nuchrs = 1;
	fc_cd->sub = NOSUB;
	fc_cd->arcs = NULL;
	fc_cd->firstchr = CHR_MIN;
	fc_cd->flags = 0;

	cm->locolormap = (color *)
		MALLOC((MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));
	if (cm->locolormap == NULL)
	{
		CERR(REG_ESPACE);
		cm->cmranges = NULL;	/* 防止在 freecm 期间失败 */
		cm->hicolormap = NULL;
		return;
	}
	/* 这个 memset 依赖于 WHITE 为零： */
	memset(cm->locolormap, WHITE,
		   (MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));

	memset(cm->classbits, 0, sizeof(cm->classbits));
	cm->numcmranges = 0;
	cm->cmranges = NULL;
	cm->maxarrayrows = 4;		/* 任意初始分配 */
	cm->hiarrayrows = 1;		/* 但我们最初只有一行/列 */
	cm->hiarraycols = 1;
	cm->hicolormap = (color *) MALLOC(cm->maxarrayrows * sizeof(color));
	if (cm->hicolormap == NULL)
	{
		CERR(REG_ESPACE);
		return;
	}
	/* 将“所有其他字符”的行初始化为 WHITE */
	cm->hicolormap[0] = WHITE;
}

/*
 * freecm - 释放颜色映射中动态分配的内容
 */
static void freecm(struct colormap *fc_cm)
{
	fc_cm->magic = 0;
	if (fc_cm->cd != fc_cm->cdspace)
		FREE(fc_cm->cd);
	if (fc_cm->locolormap != NULL)
		FREE(fc_cm->locolormap);
	if (fc_cm->cmranges != NULL)
		FREE(fc_cm->cmranges);
	if (fc_cm->hicolormap != NULL)
		FREE(fc_cm->hicolormap);
}

/*
 * pg_reg_getcolor - GETCOLOR() 的慢速案例
 */
color
pg_reg_getcolor(struct colormap *fc_cm, chr fc_c)
{
	int			fc_rownum,
				fc_colnum,
				fc_low,
				fc_high;

	/* 不应将其用于 locolormap 中的字符 */
	assert(fc_c > MAX_SIMPLE_CHR);

	/*
	 * 找到它在哪一行。 颜色映射范围是按顺序排列的，因此我们可以使用
	 * 二分查找。
	 */
	fc_rownum = 0;					/* 如果没有匹配，则使用数组行零 */
	fc_low = 0;
	fc_high = fc_cm->numcmranges;
	while (fc_low < fc_high)
	{
		int			fc_middle = fc_low + (fc_high - fc_low) / 2;
		const colormaprange *cmr = &fc_cm->cmranges[fc_middle];

		if (fc_c < cmr->cmin)
			fc_high = fc_middle;
		else if (fc_c > cmr->cmax)
			fc_low = fc_middle + 1;
		else
		{
			fc_rownum = cmr->rownum;	/* 找到匹配项 */
			break;
		}
	}

	/* 
	 * 找出它所处的列 --- 这都是与地区相关的。
	 */
	if (fc_cm->hiarraycols > 1)
	{
		fc_colnum = cclass_column_index(fc_cm, fc_c);
		return fc_cm->hicolormap[fc_rownum * fc_cm->hiarraycols + fc_colnum];
	}
	else
	{
		/* 快速通道，如果没有相关的 cclasses */
		return fc_cm->hicolormap[fc_rownum];
	}
}

/* 
 * maxcolor - 报告正在使用的最大颜色编号 */
static color maxcolor(struct colormap *cm)
{
	if (CISERR())
		return COLORLESS;

	return (color) cm->max;
}

/* 
 * newcolor - 找到一个新的颜色（必须立即分配）
 * 注意：可能会重新定位 colordescs。
 */
static color					/* COLORLESS 代表错误 */
newcolor(struct colormap *cm)
{
	struct colordesc *fc_cd;
	size_t		fc_n;

	if (CISERR())
		return COLORLESS;

	if (cm->free != 0)
	{
		assert(cm->free > 0);
		assert((size_t) cm->free < cm->ncds);
		fc_cd = &cm->cd[cm->free];
		assert(UNUSEDCOLOR(fc_cd));
		assert(fc_cd->arcs == NULL);
		cm->free = fc_cd->sub;
	}
	else if (cm->max < cm->ncds - 1)
	{
		cm->max++;
		fc_cd = &cm->cd[cm->max];
	}
	else
	{
		/* 哎呀，必须分配更多 */
		struct colordesc *newCd;

		if (cm->max == MAX_COLOR)
		{
			CERR(REG_ECOLORS);
			return COLORLESS;	/* 颜色过多 */
		}

		fc_n = cm->ncds * 2;
		if (fc_n > MAX_COLOR + 1)
			fc_n = MAX_COLOR + 1;
		if (cm->cd == cm->cdspace)
		{
			newCd = (struct colordesc *) MALLOC(fc_n * sizeof(struct colordesc));
			if (newCd != NULL)
				memcpy(VS(newCd), VS(cm->cdspace), cm->ncds *
					   sizeof(struct colordesc));
		}
		else
			newCd = (struct colordesc *)
				REALLOC(cm->cd, fc_n * sizeof(struct colordesc));
		if (newCd == NULL)
		{
			CERR(REG_ESPACE);
			return COLORLESS;
		}
		cm->cd = newCd;
		cm->ncds = fc_n;
		assert(cm->max < cm->ncds - 1);
		cm->max++;
		fc_cd = &cm->cd[cm->max];
	}

	fc_cd->nschrs = 0;
	fc_cd->nuchrs = 0;
	fc_cd->sub = NOSUB;
	fc_cd->arcs = NULL;
	fc_cd->firstchr = CHR_MIN;		/* 以防没有其他设置 */
	fc_cd->flags = 0;

	return (color) (fc_cd - cm->cd);
}

/* 
 * freecolor - 释放一种颜色（必须没有弧或子颜色） */
static void freecolor(struct colormap *cm,
		  color fc_co)
{
	struct colordesc *fc_cd = &cm->cd[fc_co];
	color		fc_pco,
				fc_nco;			/* 用于自由列表扫描 */

	assert(fc_co >= 0);
	if (fc_co == WHITE)
		return;

	assert(fc_cd->arcs == NULL);
	assert(fc_cd->sub == NOSUB);
	assert(fc_cd->nschrs == 0);
	assert(fc_cd->nuchrs == 0);
	fc_cd->flags = FREECOL;

	if ((size_t) fc_co == cm->max)
	{
		while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
			cm->max--;
		assert(cm->free >= 0);
		while ((size_t) cm->free > cm->max)
			cm->free = cm->cd[cm->free].sub;
		if (cm->free > 0)
		{
			assert(cm->free < cm->max);
			fc_pco = cm->free;
			fc_nco = cm->cd[fc_pco].sub;
			while (fc_nco > 0)
				if ((size_t) fc_nco > cm->max)
				{
					/* 从自由列表中取出这一项 */
					fc_nco = cm->cd[fc_nco].sub;
					cm->cd[fc_pco].sub = fc_nco;
				}
				else
				{
					assert(fc_nco < cm->max);
					fc_pco = fc_nco;
					fc_nco = cm->cd[fc_pco].sub;
				}
		}
	}
	else
	{
		fc_cd->sub = cm->free;
		cm->free = (color) (fc_cd - cm->cd);
	}
}

/* 
 * pseudocolor - 分配一种虚假颜色，由其他方式管理 */
static color pseudocolor(struct colormap *cm)
{
	color		fc_co;
	struct colordesc *fc_cd;

	fc_co = newcolor(cm);
	if (CISERR())
		return COLORLESS;
	fc_cd = &cm->cd[fc_co];
	fc_cd->nschrs = 0;
	fc_cd->nuchrs = 1;				/* 假装它在上层映射中 */
	fc_cd->sub = NOSUB;
	fc_cd->arcs = NULL;
	fc_cd->firstchr = CHR_MIN;
	fc_cd->flags = PSEUDO;
	return fc_co;
}

/* 
 * subcolor - 为此 chr 分配一种新的子颜色（如有必要）
 *
 * 这仅适用于映射到低颜色映射的 chr。
 */
static color subcolor(struct colormap *cm, chr fc_c)
{
	color		fc_co;				/* c 的当前颜色 */
	color		fc_sco;			/* 新子颜色 */

	assert(fc_c <= MAX_SIMPLE_CHR);

	fc_co = cm->locolormap[fc_c - CHR_MIN];
	fc_sco = newsub(cm, fc_co);
	if (CISERR())
		return COLORLESS;
	assert(fc_sco != COLORLESS);

	if (fc_co == fc_sco)				/* 已经在一个开放的子颜色中 */
		return fc_co;				/* 其余部分是多余的 */
	cm->cd[fc_co].nschrs--;
	if (cm->cd[fc_sco].nschrs == 0)
		cm->cd[fc_sco].firstchr = fc_c;
	cm->cd[fc_sco].nschrs++;
	cm->locolormap[fc_c - CHR_MIN] = fc_sco;
	return fc_sco;
}

/* 
 * subcolorhi - 为此 colormap 项分配一种新的子颜色（如有必要）
 *
 * 这与 subcolor() 的处理相同，但用于高色
 * colormap 中的条目，这些条目不一定对应于确切的一个 chr 编码。
 */
static color subcolorhi(struct colormap *cm, color *fc_pco)
{
	color		fc_co;				/* 条目的当前颜色 */
	color		fc_sco;			/* 新子颜色 */

	fc_co = *fc_pco;
	fc_sco = newsub(cm, fc_co);
	if (CISERR())
		return COLORLESS;
	assert(fc_sco != COLORLESS);

	if (fc_co == fc_sco)				/* 已经在一个开放的子颜色中 */
		return fc_co;				/* 其余部分是多余的 */
	cm->cd[fc_co].nuchrs--;
	cm->cd[fc_sco].nuchrs++;
	*fc_pco = fc_sco;
	return fc_sco;
}

/* 
 * newsub - 为颜色分配一种新的子颜色（如有必要） */
static color newsub(struct colormap *cm,
	   color fc_co)
{
	color		sco;			/* 新子颜色 */

	sco = cm->cd[fc_co].sub;
	if (sco == NOSUB)
	{							/* 颜色没有开放的子颜色 */
		/* 优化：单次引用的颜色不需要子颜色 */
		if ((cm->cd[fc_co].nschrs + cm->cd[fc_co].nuchrs) == 1)
			return fc_co;
		sco = newcolor(cm);		/* 必须创建子颜色 */
		if (sco == COLORLESS)
		{
			assert(CISERR());
			return COLORLESS;
		}
		cm->cd[fc_co].sub = sco;
		cm->cd[sco].sub = sco;	/* 开放的子颜色指向自身 */
	}
	assert(sco != NOSUB);

	return sco;
}

/* 
 * newhicolorrow - 获取 hicolormap 中的新行，从 oldrow 克隆 */
static int newhicolorrow(struct colormap *cm,
			  int fc_oldrow)
{
	int			fc_newrow = cm->hiarrayrows;
	color	   *fc_newrowptr;
	int			fc_i;

	/* 
 * 返回新行的数组索引。 注意数组可能会移动。 */
	if (fc_newrow >= cm->maxarrayrows)
	{
		color	   *fc_newarray;

		if (cm->maxarrayrows >= INT_MAX / (cm->hiarraycols * 2))
		{
			CERR(REG_ESPACE);
			return 0;
		}
		fc_newarray = (color *) REALLOC(cm->hicolormap,
									 cm->maxarrayrows * 2 *
									 cm->hiarraycols * sizeof(color));
		if (fc_newarray == NULL)
		{
			CERR(REG_ESPACE);
			return 0;
		}
		cm->hicolormap = fc_newarray;
		cm->maxarrayrows *= 2;
	}
	cm->hiarrayrows++;

	/* 分配一个新的数组行索引，视需要扩大存储 */
	fc_newrowptr = &cm->hicolormap[fc_newrow * cm->hiarraycols];
	memcpy(fc_newrowptr,
		   &cm->hicolormap[fc_oldrow * cm->hiarraycols],
		   cm->hiarraycols * sizeof(color));

	/* 复制旧行数据 */
	for (fc_i = 0; fc_i < cm->hiarraycols; fc_i++)
		cm->cd[fc_newrowptr[fc_i]].nuchrs++;

	return fc_newrow;
}

/*
 * newhicolorcols - 在高色彩图中创建一组新列
 *
 * 本质上，向右扩展二维数组并复制其自身。
 */
static void newhicolorcols(struct colormap *cm)
{
	color	   *fc_newarray;
	int			fc_r,
				fc_c;

	if (cm->hiarraycols >= INT_MAX / (cm->maxarrayrows * 2))
	{
		CERR(REG_ESPACE);
		return;
	}
	fc_newarray = (color *) REALLOC(cm->hicolormap,
								 cm->maxarrayrows *
								 cm->hiarraycols * 2 * sizeof(color));
	if (fc_newarray == NULL)
	{
		CERR(REG_ESPACE);
		return;
	}
	cm->hicolormap = fc_newarray;

	/* 复制现有列到右侧，并增加引用计数 */
	/* 必须反向处理数组，因为我们在原地重新分配了内存 */
	for (fc_r = cm->hiarrayrows - 1; fc_r >= 0; fc_r--)
	{
		color	   *fc_oldrowptr = &fc_newarray[fc_r * cm->hiarraycols];
		color	   *fc_newrowptr = &fc_newarray[fc_r * cm->hiarraycols * 2];
		color	   *fc_newrowptr2 = fc_newrowptr + cm->hiarraycols;

		for (fc_c = 0; fc_c < cm->hiarraycols; fc_c++)
		{
			color		fc_co = fc_oldrowptr[fc_c];

			fc_newrowptr[fc_c] = fc_newrowptr2[fc_c] = fc_co;
			cm->cd[fc_co].nuchrs++;
		}
	}

	cm->hiarraycols *= 2;
}

/*
 * subcolorcvec - 为 cvec 成员分配新的子颜色，填充弧线
 *
 * 对于每个由 cvec 表示的字符 "c"，执行类似于
 * newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp);
 *
 * 请注意，在典型情况下，许多子颜色都是相同的。
 * 尽管 newarc() 会丢弃重复的弧线请求，但我们可以通过
 * 不重复调用它来节省一些循环。这是
 * 通过“lastsubcolor”状态变量机械化的。
 */
static void subcolorcvec(struct vars *v,
			 struct cvec *fc_cv,
			 struct state *fc_lp,
			 struct state *fc_rp)
{
	struct colormap *cm = v->cm;
	color		fc_lastsubcolor = COLORLESS;
	chr			fc_ch,
				fc_from,
				fc_to;
	const chr  *fc_p;
	int			fc_i;

	/* 普通字符 */
	for (fc_p = fc_cv->chrs, fc_i = fc_cv->nchrs; fc_i > 0; fc_p++, fc_i--)
	{
		fc_ch = *fc_p;
		subcoloronechr(v, fc_ch, fc_lp, fc_rp, &fc_lastsubcolor);
		NOERR();
	}

	/* 和范围 */
	for (fc_p = fc_cv->ranges, fc_i = fc_cv->nranges; fc_i > 0; fc_p += 2, fc_i--)
	{
		fc_from = *fc_p;
		fc_to = *(fc_p + 1);
		if (fc_from <= MAX_SIMPLE_CHR)
		{
			/* 逐个处理简单字符 */
			chr			fc_lim = (fc_to <= MAX_SIMPLE_CHR) ? fc_to : MAX_SIMPLE_CHR;

			while (fc_from <= fc_lim)
			{
				color		fc_sco = subcolor(cm, fc_from);

				NOERR();
				if (fc_sco != fc_lastsubcolor)
				{
					newarc(v->nfa, PLAIN, fc_sco, fc_lp, fc_rp);
					NOERR();
					fc_lastsubcolor = fc_sco;
				}
				fc_from++;
			}
		}
		/* 处理范围中高于 MAX_SIMPLE_CHR 的任何部分 */
		if (fc_from < fc_to)
			subcoloronerange(v, fc_from, fc_to, fc_lp, fc_rp, &fc_lastsubcolor);
		else if (fc_from == fc_to)
			subcoloronechr(v, fc_from, fc_lp, fc_rp, &fc_lastsubcolor);
		NOERR();
	}

	/* 以及处理任意的字符类别（cclass） */
	if (fc_cv->cclasscode >= 0)
	{
		int			fc_classbit;
		color	   *fc_pco;
		int			fc_r,
					fc_c;

		/* 如果我们没有为字符类别分配列位，则扩大数组 */
		if (cm->classbits[fc_cv->cclasscode] == 0)
		{
			cm->classbits[fc_cv->cclasscode] = cm->hiarraycols;
			newhicolorcols(cm);
			NOERR();
		}
		/* 应用 subcolorhi() 并为相关列中的每个条目制作弧线 */
		fc_classbit = cm->classbits[fc_cv->cclasscode];
		fc_pco = cm->hicolormap;
		for (fc_r = 0; fc_r < cm->hiarrayrows; fc_r++)
		{
			for (fc_c = 0; fc_c < cm->hiarraycols; fc_c++)
			{
				if (fc_c & fc_classbit)
				{
					color		sco = subcolorhi(cm, fc_pco);

					NOERR();
					/* 如果需要，则添加弧线 */
					if (sco != fc_lastsubcolor)
					{
						newarc(v->nfa, PLAIN, sco, fc_lp, fc_rp);
						NOERR();
						fc_lastsubcolor = sco;
					}
				}
				fc_pco++;
			}
		}
	}
}

/*
 * subcoloronechr - 为单个字符执行 subcolorcvec 的工作
 *
 * 我们可以让 subcoloronerange 来做这个，但如果利用单字符情况
 * 会更高效。此外，调用者发现这个功能可以同时处理
 * 低字符和高级字符代码是很有用的。
 */
static void subcoloronechr(struct vars *v,
			   chr fc_ch,
			   struct state *fc_lp,
			   struct state *fc_rp,
			   color *fc_lastsubcolor)
{
	struct colormap *cm = v->cm;
	colormaprange *fc_newranges;
	int			fc_numnewranges;
	colormaprange *fc_oldrange;
	int			fc_oldrangen;
	int			fc_newrow;

	/* 处理低字符代码的简单情况 */
	if (fc_ch <= MAX_SIMPLE_CHR)
	{
		color		fc_sco = subcolor(cm, fc_ch);

		NOERR();
		if (fc_sco != *fc_lastsubcolor)
		{
			newarc(v->nfa, PLAIN, fc_sco, fc_lp, fc_rp);
			*fc_lastsubcolor = fc_sco;
		}
		return;
	}

	/*
	 * 潜在地，如果给定字符位于某个现有范围的中间，我们可能需要
	 * 比现在多两个 colormapranges。
	 */
	fc_newranges = (colormaprange *)
		MALLOC((cm->numcmranges + 2) * sizeof(colormaprange));
	if (fc_newranges == NULL)
	{
		CERR(REG_ESPACE);
		return;
	}
	fc_numnewranges = 0;

	/* 目标之前的范围保持不变 */
	for (fc_oldrange = cm->cmranges, fc_oldrangen = 0;
		 fc_oldrangen < cm->numcmranges;
		 fc_oldrange++, fc_oldrangen++)
	{
		if (fc_oldrange->cmax >= fc_ch)
			break;
		fc_newranges[fc_numnewranges++] = *fc_oldrange;
	}

	/* 将目标字符与当前范围进行匹配 */
	if (fc_oldrangen >= cm->numcmranges || fc_oldrange->cmin > fc_ch)
	{
		/* 字符不属于任何现有范围，创建一个新范围 */
		fc_newranges[fc_numnewranges].cmin = fc_ch;
		fc_newranges[fc_numnewranges].cmax = fc_ch;
		/* 行状态应从“所有其他”行中克隆 */
		fc_newranges[fc_numnewranges].rownum = fc_newrow = newhicolorrow(cm, 0);
		fc_numnewranges++;
	}
	else if (fc_oldrange->cmin == fc_oldrange->cmax)
	{
		/* 我们有一个现有的单字符范围与字符匹配 */
		fc_newranges[fc_numnewranges++] = *fc_oldrange;
		fc_newrow = fc_oldrange->rownum;
		/* 我们现在已经完全处理了这个旧范围 */
		fc_oldrange++, fc_oldrangen++;
	}
	else
	{
		/* 字符是这个现有范围的子集，必须将其拆分 */
		if (fc_ch > fc_oldrange->cmin)
		{
			/* 在字符之前发出旧范围的部分 */
			fc_newranges[fc_numnewranges].cmin = fc_oldrange->cmin;
			fc_newranges[fc_numnewranges].cmax = fc_ch - 1;
			fc_newranges[fc_numnewranges].rownum = fc_oldrange->rownum;
			fc_numnewranges++;
		}
		/* 将字符发出为单字符范围，最初从范围克隆 */
		fc_newranges[fc_numnewranges].cmin = fc_ch;
		fc_newranges[fc_numnewranges].cmax = fc_ch;
		fc_newranges[fc_numnewranges].rownum = fc_newrow =
			newhicolorrow(cm, fc_oldrange->rownum);
		fc_numnewranges++;
		if (fc_ch < fc_oldrange->cmax)
		{
			/* 发出字符之后的旧范围部分 */
			fc_newranges[fc_numnewranges].cmin = fc_ch + 1;
			fc_newranges[fc_numnewranges].cmax = fc_oldrange->cmax;
			/* 如果我们从旧的范围中制作两个新范围，则必须克隆行 */
			fc_newranges[fc_numnewranges].rownum =
				(fc_ch > fc_oldrange->cmin) ? newhicolorrow(cm, fc_oldrange->rownum) :
				fc_oldrange->rownum;
			fc_numnewranges++;
		}
		/* 我们现在已经完全处理了这个旧范围 */
		fc_oldrange++, fc_oldrangen++;
	}

	/* 更新新行中的颜色并根据需要创建弧线 */
	subcoloronerow(v, fc_newrow, fc_lp, fc_rp, fc_lastsubcolor);

	/* 目标之后的范围保持不变 */
	for (; fc_oldrangen < cm->numcmranges; fc_oldrange++, fc_oldrangen++)
	{
		fc_newranges[fc_numnewranges++] = *fc_oldrange;
	}

	/* 确保我们的原始空间估计是足够的 */
	assert(fc_numnewranges <= (cm->numcmranges + 2));

	/* 最后，将更新的范围列表存回 */
	if (cm->cmranges != NULL)
		FREE(cm->cmranges);
	cm->cmranges = fc_newranges;
	cm->numcmranges = fc_numnewranges;
}

/*
 * subcoloronerange - 为高范围执行 subcolorcvec 的工作
 */
static void subcoloronerange(struct vars *v,
				 chr fc_from,
				 chr fc_to,
				 struct state *fc_lp,
				 struct state *fc_rp,
				 color *fc_lastsubcolor)
{
	struct colormap *cm = v->cm;
	colormaprange *fc_newranges;
	int			fc_numnewranges;
	colormaprange *fc_oldrange;
	int			fc_oldrangen;
	int			fc_newrow;

	/* 调用者应处理非高范围案例 */
	assert(fc_from > MAX_SIMPLE_CHR);
	assert(fc_from < fc_to);

	/*
	 * 如果我们有 N 个不相邻的范围，可能需要多达
	 * 2N+1 个结果范围（考虑新范围覆盖所有范围的情况）。
	 */
	fc_newranges = (colormaprange *)
		MALLOC((cm->numcmranges * 2 + 1) * sizeof(colormaprange));
	if (fc_newranges == NULL)
	{
		CERR(REG_ESPACE);
		return;
	}
	fc_numnewranges = 0;

	/* 目标之前的范围保持不变 */
	for (fc_oldrange = cm->cmranges, fc_oldrangen = 0;
		 fc_oldrangen < cm->numcmranges;
		 fc_oldrange++, fc_oldrangen++)
	{
		if (fc_oldrange->cmax >= fc_from)
			break;
		fc_newranges[fc_numnewranges++] = *fc_oldrange;
	}

	/*
	 * 处理（部分）重叠目标的范围。当我们处理
	 * 每个这样的范围时，增加 "from" 以从目标范围中移除已处理的字符。
	 */
	while (fc_oldrangen < cm->numcmranges && fc_oldrange->cmin <= fc_to)
	{
		if (fc_from < fc_oldrange->cmin)
		{
			/* 处理新范围中与旧范围无对应部分 */
			fc_newranges[fc_numnewranges].cmin = fc_from;
			fc_newranges[fc_numnewranges].cmax = fc_oldrange->cmin - 1;
			/* 行状态应从“所有其他”行中克隆 */
			fc_newranges[fc_numnewranges].rownum = fc_newrow = newhicolorrow(cm, 0);
			fc_numnewranges++;
			/* 更新新行中的颜色并根据需要创建弧线 */
			subcoloronerow(v, fc_newrow, fc_lp, fc_rp, fc_lastsubcolor);
			/* 我们现在已完全处理新范围中旧范围之前的部分 */
			fc_from = fc_oldrange->cmin;
		}

		if (fc_from <= fc_oldrange->cmin && fc_to >= fc_oldrange->cmax)
		{
			/* 旧范围完全包含在新范围内，原地处理它 */
			fc_newranges[fc_numnewranges++] = *fc_oldrange;
			fc_newrow = fc_oldrange->rownum;
			fc_from = fc_oldrange->cmax + 1;
		}
		else
		{
			/* 旧范围的某部分与新范围不重叠 */
			if (fc_from > fc_oldrange->cmin)
			{
				/* 在新范围之前发出旧范围的部分 */
				fc_newranges[fc_numnewranges].cmin = fc_oldrange->cmin;
				fc_newranges[fc_numnewranges].cmax = fc_from - 1;
				fc_newranges[fc_numnewranges].rownum = fc_oldrange->rownum;
				fc_numnewranges++;
			}
			/* 发出公共子范围，最初从旧范围克隆 */
			fc_newranges[fc_numnewranges].cmin = fc_from;
			fc_newranges[fc_numnewranges].cmax =
				(fc_to < fc_oldrange->cmax) ? fc_to : fc_oldrange->cmax;
			fc_newranges[fc_numnewranges].rownum = fc_newrow =
				newhicolorrow(cm, fc_oldrange->rownum);
			fc_numnewranges++;
			if (fc_to < fc_oldrange->cmax)
			{
				/* 在新范围之后发出旧范围的部分 */
				fc_newranges[fc_numnewranges].cmin = fc_to + 1;
				fc_newranges[fc_numnewranges].cmax = fc_oldrange->cmax;
				/* 如果我们从旧的范围中制作两个新范围，则必须克隆行 */
				fc_newranges[fc_numnewranges].rownum =
					(fc_from > fc_oldrange->cmin) ? newhicolorrow(cm, fc_oldrange->rownum) :
					fc_oldrange->rownum;
				fc_numnewranges++;
			}
			fc_from = fc_oldrange->cmax + 1;
		}
		/* 更新新行中的颜色并根据需要创建弧线 */
		subcoloronerow(v, fc_newrow, fc_lp, fc_rp, fc_lastsubcolor);
		/* 我们现在已经完全处理了这个旧范围 */
		fc_oldrange++, fc_oldrangen++;
	}

	if (fc_from <= fc_to)
	{
		/* 处理新范围中与旧范围无对应部分 */
		fc_newranges[fc_numnewranges].cmin = fc_from;
		fc_newranges[fc_numnewranges].cmax = fc_to;
		/* 行状态应从“所有其他”行中克隆 */
		fc_newranges[fc_numnewranges].rownum = fc_newrow = newhicolorrow(cm, 0);
		fc_numnewranges++;
		/* 更新新行中的颜色并根据需要创建弧线 */
		subcoloronerow(v, fc_newrow, fc_lp, fc_rp, fc_lastsubcolor);
	}

	/* 目标之后的范围保持不变 */
	for (; fc_oldrangen < cm->numcmranges; fc_oldrange++, fc_oldrangen++)
	{
		fc_newranges[fc_numnewranges++] = *fc_oldrange;
	}

	/* 确保我们的原始空间估计是足够的 */
	assert(fc_numnewranges <= (cm->numcmranges * 2 + 1));

	/* 最后，将更新的范围列表存回 */
	if (cm->cmranges != NULL)
		FREE(cm->cmranges);
	cm->cmranges = fc_newranges;
	cm->numcmranges = fc_numnewranges;
}

/*
 * subcoloronerow - 为高色图中一行的新行执行 subcolorcvec 的工作
 */
static void subcoloronerow(struct vars *v,
			   int fc_rownum,
			   struct state *fc_lp,
			   struct state *fc_rp,
			   color *fc_lastsubcolor)
{
	struct colormap *cm = v->cm;
	color	   *fc_pco;
	int			fc_i;

	/* 应用 subcolorhi() 并为行中的每个条目创建弧 */
	fc_pco = &cm->hicolormap[fc_rownum * cm->hiarraycols];
	for (fc_i = 0; fc_i < cm->hiarraycols; fc_pco++, fc_i++)
	{
		color		sco = subcolorhi(cm, fc_pco);

		NOERR();
		/* 如果需要，则创建弧 */
		if (sco != *fc_lastsubcolor)
		{
			newarc(v->nfa, PLAIN, sco, fc_lp, fc_rp);
			NOERR();
			*fc_lastsubcolor = sco;
		}
	}
}

/*
 * okcolors - 将 subcolor 提升为完整颜色
 */
static void okcolors(struct nfa *fc_nfa,
		 struct colormap *cm)
{
	struct colordesc *fc_cd;
	struct colordesc *fc_end = CDEND(cm);
	struct colordesc *fc_scd;
	struct arc *fc_a;
	color		fc_co;
	color		fc_sco;

	for (fc_cd = cm->cd, fc_co = 0; fc_cd < fc_end; fc_cd++, fc_co++)
	{
		fc_sco = fc_cd->sub;
		if (UNUSEDCOLOR(fc_cd) || fc_sco == NOSUB)
		{
			/* 没有 subcolor，无需进一步操作 */
		}
		else if (fc_sco == fc_co)
		{
			/* 是 subcolor，交给父级处理 */
		}
		else if (fc_cd->nschrs == 0 && fc_cd->nuchrs == 0)
		{
			/*
			 * 父级现在为空，所以只需将它的所有弧更改为
			 * subcolor，然后释放父级。
			 *
			 * 很显然，仅仅以这种方式重新标记弧是否可行并不明显；
			 * 这似乎有风险创建重复的弧。我们基本上依赖于
			 * 处理括号表达式不能在括号的端点之间创建
			 * 同时包含颜色及其 subcolor 的弧的假设。
			 */
			fc_cd->sub = NOSUB;
			fc_scd = &cm->cd[fc_sco];
			assert(fc_scd->nschrs > 0 || fc_scd->nuchrs > 0);
			assert(fc_scd->sub == fc_sco);
			fc_scd->sub = NOSUB;
			while ((fc_a = fc_cd->arcs) != NULL)
			{
				assert(fc_a->co == fc_co);
				uncolorchain(cm, fc_a);
				fc_a->co = fc_sco;
				colorchain(cm, fc_a);
			}
			freecolor(cm, fc_co);
		}
		else
		{
			/* 父级的弧必须获得平行的 subcolor 弧 */
			fc_cd->sub = NOSUB;
			fc_scd = &cm->cd[fc_sco];
			assert(fc_scd->nschrs > 0 || fc_scd->nuchrs > 0);
			assert(fc_scd->sub == fc_sco);
			fc_scd->sub = NOSUB;
			for (fc_a = fc_cd->arcs; fc_a != NULL; fc_a = fc_a->colorchain)
			{
				assert(fc_a->co == fc_co);
				newarc(fc_nfa, fc_a->type, fc_sco, fc_a->from, fc_a->to);
			}
		}
	}
}

/*
 * colorchain - 将此弧添加到其颜色的颜色链中
 */
static void colorchain(struct colormap *cm,
		   struct arc *fc_a)
{
	struct colordesc *fc_cd = &cm->cd[fc_a->co];

	assert(fc_a->co >= 0);
	if (fc_cd->arcs != NULL)
		fc_cd->arcs->colorchainRev = fc_a;
	fc_a->colorchain = fc_cd->arcs;
	fc_a->colorchainRev = NULL;
	fc_cd->arcs = fc_a;
}

/*
 * uncolorchain - 从其颜色的颜色链中删除此弧
 */
static void uncolorchain(struct colormap *cm,
			 struct arc *fc_a)
{
	struct colordesc *fc_cd = &cm->cd[fc_a->co];
	struct arc *aa = fc_a->colorchainRev;

	assert(fc_a->co >= 0);
	if (aa == NULL)
	{
		assert(fc_cd->arcs == fc_a);
		fc_cd->arcs = fc_a->colorchain;
	}
	else
	{
		assert(aa->colorchain == fc_a);
		aa->colorchain = fc_a->colorchain;
	}
	if (fc_a->colorchain != NULL)
		fc_a->colorchain->colorchainRev = aa;
	fc_a->colorchain = NULL;		/* paranoia */
	fc_a->colorchainRev = NULL;
}

/*
 * rainbow - 在指定状态之间添加所有完整颜色（除一个之外）的弧
 *
 * 如果没有例外颜色，我们现在只生成一个标记为 RAINBOW 的弧，
 * 省去后续大量的弧处理。
 */
static void rainbow(struct nfa *fc_nfa,
		struct colormap *cm,
		int fc_type,
		color fc_but,				/* 如果没有例外则为 COLORLESS */
		struct state *fc_from,
		struct state *fc_to)
{
	struct colordesc *fc_cd;
	struct colordesc *fc_end = CDEND(cm);
	color		fc_;

	if (fc_but == COLORLESS)
	{
		newarc(fc_nfa, fc_type, RAINBOW, fc_from, fc_to);
		return;
	}

	/* 必须以困难的方式完成。跳过 subcolors、pseudocolors 和 "but" */
	for (fc_cd = cm->cd, fc_ = 0; fc_cd < fc_end && !CISERR(); fc_cd++, fc_++)
		if (!UNUSEDCOLOR(fc_cd) && fc_cd->sub != fc_ && fc_ != fc_but &&
			!(fc_cd->flags & PSEUDO))
			newarc(fc_nfa, fc_type, fc_, fc_from, fc_to);
}

/*
 * colorcomplement - 添加互补颜色的弧
 *
 * 我们添加所有不是伪颜色并且不匹配
 * 任何 “of” 状态的 PLAIN outarcs 的颜色的弧。
 *
 * 调用顺序应该与 cloneouts() 协调。
 */
static void colorcomplement(struct nfa *fc_nfa,
				struct colormap *cm,
				int fc_type,
				struct state *fc_of,
				struct state *fc_from,
				struct state *fc_to)
{
	struct colordesc *fc_cd;
	struct colordesc *fc_end = CDEND(cm);
	color		fc_co;
	struct arc *fc_a;

	assert(fc_of != fc_from);

	/*
	 * 一个 RAINBOW 弧匹配所有颜色，使补集为空。但我们
	 * 不能只返回而不创建任何弧，因为那样会使 NFA 断开，
	 * 这会破坏未来的 delsub()。相反，创建
	 * 一个 CANTMATCH 弧。同时设置 HASCANTMATCH 标志，以便我们知道
	 * 在 NFA 优化开始时需要清理它。
	 */
	if (findarc(fc_of, PLAIN, RAINBOW) != NULL)
	{
		newarc(fc_nfa, CANTMATCH, 0, fc_from, fc_to);
		fc_nfa->flags |= HASCANTMATCH;
		return;
	}

	/* 否则，暂时标记在 of 的 out-arcs 中出现的颜色 */
	for (fc_a = fc_of->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (fc_a->type == PLAIN)
		{
			assert(fc_a->co >= 0);
			fc_cd = &cm->cd[fc_a->co];
			assert(!UNUSEDCOLOR(fc_cd));
			fc_cd->flags |= COLMARK;
		}

		/*
		 * 这里没有重新互补颜色集的语法，所以我们不能
		 * 在这里看到 CANTMATCH 弧。
		 */
		assert(fc_a->type != CANTMATCH);
	}

	/* 扫描颜色，清除暂时标记，为未标记颜色添加弧 */
	for (fc_cd = cm->cd, fc_co = 0; fc_cd < fc_end && !CISERR(); fc_cd++, fc_co++)
	{
		if (fc_cd->flags & COLMARK)
			fc_cd->flags &= ~COLMARK;
		else if (!UNUSEDCOLOR(fc_cd) && !(fc_cd->flags & PSEUDO))
			newarc(fc_nfa, fc_type, fc_co, fc_from, fc_to);
	}
}


#ifdef REG_DEBUG

/*
 * dumpcolors - 调试输出
 */
static void dumpcolors(struct colormap *cm,
		   FILE *fc_f)
{
	struct colordesc *fc_cd;
	struct colordesc *fc_end;
	color		fc_co;
	chr			fc_c;

	fprintf(fc_f, "max %ld\n", (long) cm->max);
	fc_end = CDEND(cm);
	for (fc_cd = cm->cd + 1, fc_co = 1; fc_cd < fc_end; fc_cd++, fc_co++) /* skip 0 */
	{
		if (!UNUSEDCOLOR(fc_cd))
		{
			assert(fc_cd->nschrs > 0 || fc_cd->nuchrs > 0);
			if (fc_cd->flags & PSEUDO)
				fprintf(fc_f, "#%2ld(ps): ", (long) fc_co);
			else
				fprintf(fc_f, "#%2ld(%2d): ", (long) fc_co, fc_cd->nschrs + fc_cd->nuchrs);

			/*
			 * 不幸的是，接下来的这一部分很难更高效地完成。
			 */
			for (fc_c = CHR_MIN; fc_c <= MAX_SIMPLE_CHR; fc_c++)
				if (GETCOLOR(cm, fc_c) == fc_co)
					dumpchr(fc_c, fc_f);
			fprintf(fc_f, "\n");
		}
	}
	/* 如果高颜色映射中包含任何有趣的内容，则转储它 */
	if (cm->hiarrayrows > 1 || cm->hiarraycols > 1)
	{
		int			fc_r,
					fc_c;
		const color *fc_rowptr;

		fprintf(fc_f, "other:\t");
		for (fc_c = 0; fc_c < cm->hiarraycols; fc_c++)
		{
			fprintf(fc_f, "\t%ld", (long) cm->hicolormap[fc_c]);
		}
		fprintf(fc_f, "\n");
		for (fc_r = 0; fc_r < cm->numcmranges; fc_r++)
		{
			dumpchr(cm->cmranges[fc_r].cmin, fc_f);
			fprintf(fc_f, "..");
			dumpchr(cm->cmranges[fc_r].cmax, fc_f);
			fprintf(fc_f, ":");
			fc_rowptr = &cm->hicolormap[cm->cmranges[fc_r].rownum * cm->hiarraycols];
			for (fc_c = 0; fc_c < cm->hiarraycols; fc_c++)
			{
				fprintf(fc_f, "\t%ld", (long) fc_rowptr[fc_c]);
			}
			fprintf(fc_f, "\n");
		}
	}
}

/*
 * dumpchr - 打印一个字符
 *
 * 有点以字符为中心，但足以用于调试。
 */
static void dumpchr(chr fc_c,
		FILE *fc_f)
{
	if (fc_c == '\\')
		fprintf(fc_f, "\\\\");
	else if (fc_c > ' ' && fc_c <= '~')
		putc((char) fc_c, fc_f);
	else
		fprintf(fc_f, "\\u%04lx", (long) fc_c);
}

#endif							/* REG_DEBUG */
